Word break II

Time: O(NxL^2+NxR); Space: O(N^2); hard

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Notes:

  • The same word in the dictionary may be reused multiple times in the segmentation.

  • You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = “catsanddog”, wordDict = [“cat”, “cats”, “and”, “sand”, “dog”]

Output:

[
  "cats and dog",
  "cat sand dog"
]

Example 2:

Input: s = “pineapplepenapple”, wordDict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”]

Output:

[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]

Explanation:

  • Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]

Output: []

[1]:

class Solution1(object):
    """
    Time: O(N*L^2+N*R), L is the max length of the words, R is the number of the results.
    Space: O(N^2)
    """
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: List[str]
        """
        n = len(s)

        max_len = 0
        for string in wordDict:
            max_len = max(max_len, len(string))

        can_break = [False for _ in range(n + 1)]
        valid = [[False] * n for _ in range(n)]
        can_break[0] = True
        for i in range(1, n + 1):
            for l in range(1, min(i, max_len) + 1):
                if can_break[i-l] and s[i-l:i] in wordDict:
                    valid[i-l][i-1] = True
                    can_break[i] = True

        result = []
        if can_break[-1]:
            self.wordBreakHelper(s, valid, 0, [], result)
        return result

    def wordBreakHelper(self, s, valid, start, path, result):
        if start == len(s):
            result.append(" ".join(path))
            return
        for i in range(start, len(s)):
            if valid[start][i]:
                path += [s[start:i+1]]
                self.wordBreakHelper(s, valid, i + 1, path, result)
                path.pop()

[5]:

sol = Solution1()

s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
assert sol.wordBreak(s, wordDict) == ["cats and dog","cat sand dog"] or ["cat sand dog", "cats and dog"]


s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
# print(sol.wordBreak(s, wordDict))
assert sol.wordBreak(s, wordDict) == [
  "pine apple pen apple",
  "pine applepen apple",
  "pineapple pen apple",
]

s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
assert sol.wordBreak(s, wordDict) == []